#include "QuadTree.h"
#include "Entity.h"

QuadTree::QuadTree(const QList<Entity *> &entities, const QPoint &center, float length, float height, int splitSize)
{
  build(entities, center, length, height, splitSize);
}

QuadTree::~QuadTree() {}

void QuadTree::build(const QList<Entity *> &entities, const QPoint &center, float length, float height, int splitSize)
{
  mRoot = new QuadTreeNode(entities, center, length, height, splitSize);
}

void QuadTree::addEntities(const QList<Entity *> &entities)
{
  mRoot->addEntities(entities);
}

void QuadTree::addEntity(Entity *entity)
{
  mRoot->addEntity(entity);
}

QList<Entity*> QuadTree::getEntitiesInRadius(const QPoint &position, int range)
{
  QList<Entity*> container;
  getEntitiesInRadius(position, range, container);
  return container;
}

void QuadTree::getEntitiesInRadius(const QPoint &position, int range, QList<Entity *> &container)
{
  mRoot->getEntitiesInRadius(position, range, container);
}


QuadTree::QuadTreeNode::QuadTreeNode(const QPoint &center, float length, float height, int splitSize, QuadTreeNode *parent)
  : mParent(parent),
    mTopLeftChild(NULL),
    mTopRightChild(NULL),
    mBottomLeftChild(NULL),
    mBottomRightChild(NULL),
    mLength(length),
    mHeight(height),
    mSplitSize(splitSize),
    mIsSplit(false),
    mCenter(center),
    mTopLeftPosition(mCenter.x() - mLength/2, mCenter.y() - mHeight/2),
    mTopRightPosition(mCenter.x() + mLength/2, mCenter.y() - mHeight/2),
    mBottomLeftPosition(mCenter.x() - mLength/2, mCenter.y() + mHeight/2),
    mBottomRightPosition(mCenter.x() +- mLength/2, mCenter.y() + mHeight/2)
{
}

QuadTree::QuadTreeNode::QuadTreeNode(const QList<Entity *> &entities,
                                     const QPoint &center,
                                     float length,
                                     float height,
                                     int splitSize,
                                     QuadTreeNode *parent)
  : mParent(parent),
    mTopLeftChild(NULL),
    mTopRightChild(NULL),
    mBottomLeftChild(NULL),
    mBottomRightChild(NULL),
    mLength(length),
    mHeight(height),
    mSplitSize(splitSize),
    mIsSplit(false),
    mCenter(center),
    mTopLeftPosition(mCenter.x() - mLength/2, mCenter.y() - mHeight/2),
    mTopRightPosition(mCenter.x() + mLength/2, mCenter.y() - mHeight/2),
    mBottomLeftPosition(mCenter.x() - mLength/2, mCenter.y() + mHeight/2),
    mBottomRightPosition(mCenter.x() +- mLength/2, mCenter.y() + mHeight/2)
{
  addEntities(entities);
}

void QuadTree::QuadTreeNode::addEntities(const QList<Entity*>& entities)
{
  foreach (Entity* entity, entities)
    addEntity(entity);
}

void QuadTree::QuadTreeNode::addEntity(Entity* entity)
{
  if (!mIsSplit)
  {
    if (mEntities.size()+1 > mSplitSize)
    {
      split();
      addEntity(entity);
    }
    else
    {
      mEntities << entity;
    }
  }
  else
  {
    if (mTopLeftChild->wouldContain(entity->position()))
    {
      mTopLeftChild->addEntity(entity);
    }
    else if (mTopRightChild->wouldContain(entity->position()))
    {
      mTopRightChild->addEntity(entity);
    }
    else if (mBottomLeftChild->wouldContain(entity->position()))
    {
      mBottomLeftChild->addEntity(entity);
    }
    else if (mBottomRightChild->wouldContain(entity->position()))
    {
      mBottomRightChild->addEntity(entity);
    }
  }
}

void QuadTree::QuadTreeNode::getEntitiesInRadius(const QPoint& position, int range, QList<Entity*>& container)
{
  if (!isInRange(position, range))
  {
    return;
  }
  else if (mIsSplit)
  {
    mTopLeftChild->getEntitiesInRadius(position, range, container);
    mTopRightChild->getEntitiesInRadius(position, range, container);
    mBottomLeftChild->getEntitiesInRadius(position, range, container);
    mBottomRightChild->getEntitiesInRadius(position, range, container);
  }
  else
  {
    foreach (Entity *entity, mEntities)
    {
      if ((entity->position() - position).manhattanLength() < range)
        container << entity;
    }
  }
}

void QuadTree::QuadTreeNode::split()
{
  mTopLeftChild = new QuadTreeNode(mCenter+QPoint(-mLength/4, -mHeight/4), mLength/2, mHeight/2, mSplitSize, this);
  mTopRightChild = new QuadTreeNode(mCenter+QPoint(mLength/4, -mHeight/4), mLength/2, mHeight/2, mSplitSize, this);
  mBottomLeftChild = new QuadTreeNode(mCenter+QPoint(-mLength/4, mHeight/4), mLength/2, mHeight/2, mSplitSize, this);
  mBottomRightChild = new QuadTreeNode(mCenter+QPoint(mLength/4, mHeight/4), mLength/2, mHeight/2, mSplitSize, this);

  mIsSplit = true;

  while (mEntities.size() > 0)
  {
    addEntity(mEntities.front());
    mEntities.pop_front();
  }
}

void QuadTree::QuadTreeNode::merge()
{
  mEntities = mTopLeftChild->mEntities + mTopRightChild->mEntities +
              mBottomLeftChild->mEntities + mBottomRightChild->mEntities;

  delete mTopLeftChild;
  delete mTopRightChild;
  delete mBottomLeftChild;
  delete mBottomRightChild;
  mIsSplit = false;
}

int QuadTree::QuadTreeNode::getNumContainingEntities() const
{
  if (!mIsSplit)
  {
    return mEntities.size();
  }
  else
  {
    return mTopLeftChild->getNumContainingEntities() +
           mTopRightChild->getNumContainingEntities() +
           mBottomLeftChild->getNumContainingEntities() +
           mBottomRightChild->getNumContainingEntities();
  }
}

bool QuadTree::QuadTreeNode::isInRange(const QPoint &position, int range) const
{
  return (mTopLeftPosition - position).manhattanLength() < range ||
         (mTopRightPosition - position).manhattanLength() < range ||
         (mBottomLeftPosition - position).manhattanLength() < range ||
         (mBottomRightPosition - position).manhattanLength() < range;
}

bool QuadTree::QuadTreeNode::wouldContain(const QPoint &position) const
{
  return position.x() > mTopLeftPosition.x() && position.x() < mTopRightPosition.x() &&
         position.y() > mTopLeftPosition.y() && position.y() < mBottomLeftPosition.y();
}
